import collections
class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        stack = collections.deque()
        stack.append(0)
        for i in range(1, len(nums)):
            if nums[i] >= nums[stack[-1]]:
                stack.append(i)
            else:
                while stack:
                    if nums[stack[-1]] > nums[i]:
                        stack.pop()
                    else:
                        break
                stack.append(i)
        left_index = 0
        i = 0
        if len(stack) == len(nums):
            return 0
        while i < len(stack):
            if i == stack[i]:
                left_index += 1
                i += 1
            else:
                break
        stack = collections.deque()
        stack.append(len(nums) - 1)
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] <= nums[stack[-1]]:
                stack.append(i)
            else:
                while stack:
                    if nums[stack[-1]] < nums[i]:
                        stack.pop()
                    else:
                        break
                stack.append(i)
        right_index = 0
        i = 0
        n = len(nums)
        while i < len(stack):
            if n - 1 - i == stack[i]:
                right_index += 1
                i += 1
            else:
                break
        if right_index == 0:
            right_index = n
        else:
            right_index = stack[right_index - 1]
        return right_index - left_index


data = Solution()
nums = [2, 6, 4, 8, 10, 9, 15]
print(data.findUnsortedSubarray(nums))
nums = [1, 2, 3, 4]
print(data.findUnsortedSubarray(nums))
nums = [1]
print(data.findUnsortedSubarray(nums))
nums = [2, 1]
print(data.findUnsortedSubarray(nums))
nums = [2,3,3,2,4]
print(data.findUnsortedSubarray(nums))
nums = [2,3,3,2,7,7,10]
print(data.findUnsortedSubarray(nums))
nums = [1,2,4,5,3]
print(data.findUnsortedSubarray(nums))